package com.atwy.search;

/**
 * 插值查找，类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
 * <p>
 * 二分查找中 mid = (left + right)/2 = left + 1/2 *(right - left),二分查找就是系数是二分之一，
 * 插值查找中 mid = left + (target - array[left])/(array[right] - array[left]) *(right - left)
 * <p>
 * 举例说明：
 * 比如 array = {1,2,3,...,100},如果用二分查找 target=1，需要多少次才能找到1？
 * 而用插值查找，mid = 0+(1-1)/(100-0)*(99-0) = 0,明显降低了查找次数
 */
public class InterpolationSearch {
    public static void main(String[] args) {
        int[] array = {2, 3, 5, 9, 12, 34, 65};
        int index = search(array, 5);

        if (index == -1) {
            System.out.println("没有找到到");
        } else {
            System.out.println("找到，下标为=" + index);
        }
    }

    public static int search(int[] array, int target) {


        return interpolationSearch(array, 0, array.length - 1, target);
    }

    private static int interpolationSearch(int[] array, int left, int right, int target) {

        if (left > right || target < array[0] || target > array[array.length - 1]) {
            return -1;
        }

        // 求出 mid, 自适应
        int mid = left + (right - left) * (target - array[left]) / (array[right] - array[left]);

        int midValue = array[mid];
        if (target > midValue) {// 向右递归
            return interpolationSearch(array, mid + 1, right, target);
        } else if (target < midValue) {
            return interpolationSearch(array, left, mid - 1, target);
        }

        return mid;
    }
}
